package com.tucc.hello.tree;

import java.util.*;

/**
 * @author tucc
 * @description TODO
 * @date 2021/5/10 13:47
 **/
public class Main {

    private static int max = 0;

    public static TreeNode makeTree(List<Integer> list) {
        TreeNode root = null;
        if (list != null && list.size() > 0) {
            Deque<TreeNode> queue = new LinkedList<>();
            TreeNode cur = null;
            int state = 0;
            root = new TreeNode(list.get(0));
            queue.add(root);
            for (int i = 1; i < list.size(); i++) {
                if (cur == null) {
                    cur = queue.removeFirst();
                    state = 0;
                }
                Integer val = list.get(i);
                if (val != null) {
                    TreeNode node = new TreeNode(val);
                    queue.addLast(node);
                    if (state == 0) {
                        cur.setLeft(node);
                    } else {
                        cur.setRight(node);
                    }
                }
                state++;
                if (state == 2) {
                    state = 0;
                    cur = null;
                }
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = makeTree(Arrays.asList(1, -5, 2, 9, null, 8, 3, null, null, null, null,null,4));

//        System.out.println("\n=======pre order=======");
//        TreeNode.printPreOrder(root);
//        System.out.println("\n=======middle order=======");
//        TreeNode.printMiddleOrder(root);
//        System.out.println("\n=======post order=======");
//        TreeNode.printPostOrder(root);
//        System.out.println();

        getMaxDistance(root);
        System.out.println(max);
    }

    public static void getMaxDistance(TreeNode root) {
        if (root == null){
            return;
        }
        int l = getDistance(root.getLeft());
        int r = getDistance(root.getRight());
        if (l + r > max) {
            max = l + r;
        }
        getMaxDistance(root.getLeft());
        getMaxDistance(root.getRight());
    }

    public static int getDistance(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = getDistance(node.getLeft());
        int r = getDistance(node.getRight());
        int result = node.getVal() + Math.max(l, r);
        return result;
    }


}
